This guide refers to the hex numbers that correlate to colors the NES uses. A list of palettes can be found here: https://wiki.nesdev.com/w/images/5/59/Savtool-swatches.png

In Zelda II, it is fairly easy to find most palettes. What is more difficult is to find the palettes for Link after a spell is cast.

There are two types of spells that change Link's palette while he is on that screen: Shield (which normally turns him red) and all other spells (which also includes picking up an item).

The colors for these spells are stored at the following hex positions:

The shield spell:
This spell seems to load Link's default tunic and palette, except changes the green (2A) to red (16). The color that Link's tunic changes into can be found at ROM address at 0x000E9D.
All other spells
Brown: 0x002A0A . This is 18 by default.
Peach: 0x002A10 . This is 36 by default.
Green: 0x0010EB . This is 2A by default.

Between 2A00 and 2A10 you will also see a number of other colors used for the flashing when Link casts a spell. If you wanted to change these colors, you can do so from here.

Finding the tunic color (green by default) is rather difficult as it is not where you would expect to find it. Indeed, the code at 0x002A16 has a 2A that is seemingly for Link's tunic, but never actually loaded.

For most other palettes - including Link's default palette - you can use the PPU viewer to view the loaded palettes and then search for them in the ROM.

Special thanks to ShadowOne333 for documenting the vast majority of these addresses, and for pointing me in the right direction to find the one he hadn't.